package com.atguigu.tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

/**
 * 赫夫曼树
 */
public class HuffmanTreeDemo {

    public static void main(String[] args) {

        int arr[] = {4,2,1,8,5,6};
        ArrayList<HuffNode> huffNodes = new ArrayList<>();

        for (int i : arr) {
            HuffNode huffNode = new HuffNode(i);
            huffNodes.add(huffNode);
        }

        while (huffNodes.size()>1) {
            //完成集合的排序
            Collections.sort(huffNodes);

            //整合赫夫曼树

            HuffNode temp = new HuffNode(huffNodes.get(0).getVal() + huffNodes.get(1).getVal());
            temp.setLeftNode(huffNodes.get(0));
            temp.setRightNode(huffNodes.get(1));
            huffNodes.remove(0);
            huffNodes.remove(0);
            huffNodes.add(temp);

        }

        huffNodes.get(0).preOrder();

    }

}

class HuffNode implements Comparable<HuffNode>{
    private int val;
    private HuffNode leftNode;
    private HuffNode RightNode;

    public HuffNode(int val){
        this.val = val;
    }

    //前序遍历方法
    public void preOrder(){
        System.out.println(this);

        if (this.getLeftNode() != null){
            this.getLeftNode().preOrder();
        }

        if (this.getRightNode() != null){
            this.getRightNode().preOrder();
        }


    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public HuffNode getLeftNode() {
        return leftNode;
    }

    public void setLeftNode(HuffNode leftNode) {
        this.leftNode = leftNode;
    }

    public HuffNode getRightNode() {
        return RightNode;
    }

    public void setRightNode(HuffNode rightNode) {
        RightNode = rightNode;
    }

    @Override
    public String toString() {
        return "HuffNode{" +
                "val=" + val +
                '}';
    }

    @Override
    public int compareTo(HuffNode o) {
        return this.val-o.val;
    }
}
